import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> ret;
    public StringBuilder path;
    public String s;
    public List<String> letterCasePermutation(String ss) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        s = ss;
        dfs(0);
        return ret;
    }
    public void dfs(int index){
        //递归出口
        if(index == s.length()){
            ret.add(path.toString());
            return;
        }
        char ch = s.charAt(index);
        path.append(ch);
        dfs(index + 1);//递归
        path.deleteCharAt(path.length() - 1);

        if(ch >= 'a' && ch <= 'z'){
            char change = (char) (ch - 32);
            path.append(change);
            dfs(index + 1);
            path.deleteCharAt(path.length() - 1);
        }else if(ch >= 'A' && ch <= 'Z'){
            char change = (char) (ch + 32);
            path.append(change);
            dfs(index + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}